import heapq
import functools

class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        key = functools.cmp_to_key(lambda x,y:y-x)
        heap = []
        ret = []
        for i, num in enumerate(nums):
            heapq.heappush(heap, (key(num), i))
            if i>=k-1:
                while heap[0][1]<=i-k:
                    heapq.heappop(heap)
                ret.append(nums[heap[0][1]])
        return ret

print(Solution().maxSlidingWindow([1,3,-1,-3,5,3,6,7],3))

                    